import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Test_8_29 {


}


//力扣：155. 最小栈
class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        this.stack = new Stack<>();
        this.minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if(minStack.empty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if(!stack.empty()) {
            int top = stack.pop();
            if(top == minStack.peek()) {
                minStack.pop();
            }
        }
    }

    public int top() {
        if(!stack.empty()) {
            return stack.peek();
        }else {
            return -1;
        }
    }

    public int getMin() {
        if(!stack.empty()) {
            return minStack.peek();
        }else {
            return -1;
        }
    }
}

//力扣：622. 设计循环队列
class MyCircularQueue {

    int[] elem;
    private int front;
    private int rear;
    private int len;

    public MyCircularQueue(int k) {
        elem = new int[k+1];
        this.len = k+1;
    }

    public boolean enQueue(int value) {
        if(this.isFull()) {
            return false;
        }else {
            elem[rear] = value;
            rear = (rear + 1) % len;
            return true;
        }
    }

    public boolean deQueue() {
        if(!this.isEmpty()) {
            front = (front + 1) % len;
            return true;
        }else {
            return false;
        }
    }

    public int Front() {
        if(!this.isEmpty()) {
            return elem[front];
        }else {
            return -1;
        }
    }

    public int Rear() {
        if(!this.isEmpty()) {
            int index = (rear==0)?len-1:rear-1;
            return elem[index];
        }else {
            return -1;
        }
    }

    public boolean isEmpty() {
        if(front == rear) {
            return true;
        }
        return false;
    }

    public boolean isFull() {
        if((rear + 1) % len == front) {
            return true;
        }
        return false;
    }
}


//力扣：232. 用栈实现队列
class MyQueue {
    //定义两个栈
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        //当第2个栈不为空时，弹出第2个栈的栈顶元素；否则将第1个栈的元素全部入到第2个栈，再弹出栈顶元素
        if(stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if(stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        if(stack1.empty() && stack2.empty()) {
            return true;
        }else {
            return false;
        }
    }
}


//力扣：225. 用队列实现栈
class MyStack {

    private Queue<Integer> q1;
    private Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        if(this.empty()) {
            q1.offer(x);
        }else if(!q1.isEmpty()) {
            q1.offer(x);
        }else {
            q2.offer(x);
        }

    }

    public int pop() {
        if(!q1.isEmpty()) {
            int sz = q1.size();
            for(int i = 0; i < sz-1; i++) {
                q2.offer(q1.poll());
            }
            return q1.poll();
        }else {
            int sz = q2.size();
            for(int i = 0; i < sz-1; i++) {
                q1.offer(q2.poll());
            }
            return q2.poll();
        }
    }

    public int top() {
        if(!q1.isEmpty()) {
            int sz = q1.size();
            int tmp = -1;
            for(int i = 0; i < sz; i++) {
                q2.offer(tmp = q1.poll());
            }
            return tmp;
        }else {
            int sz = q2.size();
            int tmp = -1;
            for(int i = 0; i < sz; i++) {
                q1.offer(tmp = q2.poll());
            }
            return tmp;
        }
    }

    public boolean empty() {
        if(q1.isEmpty() && q2.isEmpty()) {
            return true;
        }
        return false;
    }
}